1. Field of the Invention
Packet communication architecture is the structuring of data processing systems as collections of physical units that communicate only by sending information packets of fixed size, using an asynchronous protocol. Each unit is designed so it never has to wait for a response to a packet it has transmitted to another unit while other packets are waiting for its attention. Packets are routed between sections of a system by networks of units arranged to sort many packets concurrently according to their destination. In this way, it is possible to arrange that system units are heavily used, provided concurrency in the task to be performed can be exploited. The packet communication principle is especially attractive for data flow processors since the execution of data flow programs readily separates into many independent computational events. The present invention relates to the use of packet communication in the architecture of memory systems capable of processing many independent memory transactions concurrently. The behavior of these memory systems is prescribed by a formal memory model appropriate to a computer system for data flow programs.
2. The Prior Art
With the advent of large scale integration (LSI) technology, one of the main directions of further advance in the power of large computer systems is through exploitation of parallelism. Attempts to achieve parallelism in array processors, associative processors and vector or pipeline machines have succeeded only with the sacrifice of programmability. These large parallel machines all require that high levels of local parallelism be expressed in program formats that retain the notion of sequential control flow. Since most algorithms do not naturally exhibit local parallelism in the form expected by these machines, intricate data representations and convoluted algorithms must be designed if the potential of the machine is to be approached.
The alternative is to design machines that can exploit the global parallelism in programs, that is, to take advantage of opportunities to execute unrelated parts of a program concurrently. Conventional sequential machine languages are unsuited to this end because identification of concurrently executable program parts is a task of great difficulty. Data flow program representations are of more interest, for only essential sequencing relationships among computational events are indicated. An instruction in a data flow program is enabled for execution by the arrival of its operand values -- there is no separate notion of control flow, and where there is no data dependence between program parts, the parts are implicitly available for parallel execution.
Several designs for data processing systems have been developed that can achieve highly parallel operation by exploiting the global concurrency of programs represented in data flow form [1-6]. Two of these designs [3, 6] are able to execute programs expressed in a conventional high-level language that exceeds Algol 60 in generality. These systems consist of units that operate independently and interact only by transmitting information packets over channels that connect pairs of units. The units themselves may have a similar structure that we call packet communication architecture.
Details of the above designated references are given below.